Error correction codes have been widely used for transmission and/or storage of data in real world environments. Such environments may introduce noise, interference, and other effects that can deteriorate the quality of the data transmitted or stored, such that upon recovery, the data may contain errors. Generally speaking, error correction coding utilizes codes to add redundancy to the data transmitted or stored so that the redundancy can later be exploited to correct errors when the data is recovered.
Traditional forward error correction (FEC) codes have been commonly adopted as error correction codes in data transmission and storage systems. These traditional FEC codes include block codes and convolutional codes. Block codes generally involve an encoder that takes in blocks of k input bits and transform each block into n output bits. Such a code is thus referred to as a (n,k) block code. The rate of such a block code is typically defined as r=k/n.
Convolutional codes generally involve an encoder having a memory of M bits. Thus, a convolutional encoder may be viewed as having 2M possible states. Each output bit of the convolutional encoder may be determined based on the memory of M bits and possibly one or more incoming bits. For example, an output bit may be generated by applying combinatorial logic to selected taps on the memory of M bits and one or more incoming bits. In other words, the output of a convolutional encoder may be determined based on the current state of the encoder and the incoming data. Also, more than one output bit may be generated in this manner each time new input bit(s) are shifted into the memory of M bits. The operation of a convolutional encoder may be represented by a trellis, as is well known in the art. The rate of a convolutional encoder that generates n output bits for every k input bits is typically defined as r=k/n.
There exists a variety of different block codes and convolutional codes. There also exists a variety of decoding algorithms for decoding the coded information in attempting to reconstruct the original data. For example, convolutional coding paired with Viterbi decoding is a popular FEC technique that is widely used in systems for transmitting data through channels affected by additive white Gaussian noise (AWGN).
Turbo codes and Turbo-like codes represent a relatively new and very powerful category of error correction codes. In the present disclosure, these codes and variations thereof are generally referred to as Turbo-like codes (TLC). A Turbo-like code generally involves the concatenation of two or more simple codes separated by an interleaver, combined with an iterative decoding strategy.
TLCs may provide significantly better coding gain compared to traditional FEC approaches. The coding gain may be as much as 3 decibels (dB) in many cases. That is, compared to a system using a traditional FEC code to achieve a certain performance level while operating at a particular noise level, a system using a TLC may be able to achieve the same performance level while operating at a noise level that is higher by 3 dB. The performance of such systems may be measured as bit error rate (BER), and the noise level may be measured as signal-to-noise ratio (Eb/N0, expressed in dB), for instance.
FIG. 1 depicts a general curve of error probability performance versus signal-to-noise ratio that is characteristic of many TLCs. As shown, there is an initial steep reduction in error probability as Eb/N0 is increased called the waterfall region, followed by a region of shallower reduction called the error floor region. The area where TLCs have traditionally excelled is in the waterfall region. Indeed, there exist TLCs that are within a small fraction of a dB of the Shannon limit in this region. However, many TLCs have an almost flat error floor region, or one that starts at a very high error rate, or both. This means that the coding gain of these TLCs rapidly diminishes as the target error rate is reduced. The performance of a TLC in the error floor region likely depends on many factors, such as the constituent code design and the interleaver design, but it typically worsens as the code rate increases or the frame size decreases. Thus many TLC designs only perform well at high error rates, or low code rates, or large frame sizes. Furthermore these designs often only target a single code rate, frame size, and modulation scheme, or suffer degraded performance or increased complexity to achieve flexibility in these areas.
A number of properties desirable in a Turbo-like code are described below. However, existing TLCs typically achieve only some of these desirable qualities, and do not consistently perform well in terms of these qualities across different environments.
Good threshold performance is desirable. That is, the waterfall region of a TLC's BER curve should occur at as low an Eb/N0 as possible. This will minimize the energy expense of transmitting information. Good floor performance is also desirable. The error floor region of a TLC's BER curve should occur at a BER of as low as possible. For communication systems employing an automatic repeat-request (ARQ) scheme this may be as high as 10−6, while most broadcast communications systems demand 10−10 performance, and storage systems and optical fiber links require BERs as low as 10−15. Low complexity code constraints are desirable. To allow for low complexity decoders, particularly for high throughput applications, the constituent codes of the TLC should be simple. Furthermore, to allow the construction of high throughput decoders, the code structure should be such that parallel decoder architectures with simple routing and memory structures are possible. Fast decoder convergence is desirable. The decoder of a TLC code should converge rapidly (i.e. the number of iterations required to achieve most of the iteration gain should be low). This allows the construction of high throughput hardware decoders and/or low complexity software decoders. Code rate flexibility is also desirable. Most modern communications and storage systems do not operate at a single code rate. For example, in adaptive systems the code rate is adjusted according to the available SNR so that the code overheads are minimized. It should be possible to fine-tune the code rate to adapt to varying application requirements and channel conditions. Furthermore, this code rate flexibility should not come at the expense of degraded threshold or floor performance. Many systems demand code rates of 0.95 or above, which is typically very difficult to achieve for most TLCs. Frame size flexibility is desirable. Generally speaking the threshold and floor performance of TLCs are maximized by maximizing frame size. However, it is not always practical, for example, to have frames of many thousands of bits. Therefore it is desirable that a TLC still performs well with smaller frame size, as small as only one or two hundred bits for instance. Furthermore, modulation flexibility is desirable. In modern communication systems employing adaptive coding and modulation (ACM), for example, it is essential that the TLC easily support a broad range of modulation schemes.
Turbo-like codes (TLCs) include Parallel Concatenated Convolutional Codes (PCCC), which is often referred to as the classical Turbo code, Serially Concatenated Convolutional Codes (SCCC), Low Density Parity Check Codes (LDPC), and Turbo Product Codes (TPC). There have also been numerous variations on the basic TLC theme. FIGS. 2-5 present some basic encoder structures for these various TLCs. A brief description of different characteristics of each of these TLCs is provided below.
FIG. 2 is an illustrative block diagram of an encoder for a PCCC which involves the parallel concatenation of two convolutional codes. One encoder is fed the frame of information bits directly, while the other encoder is fed an interleaved version of the information bits. The encoded outputs of the two encoders are mapped to the signal set used on the channel. PCCCs generally have good threshold performance that is amongst the best threshold performance of all TLCs. However, PCCCs also generally have the worst floor performance of all TLCs. With 8-state constituent codes BER floors are typically in the range 10−6 to 10−8, but this can be reduced to the 10−8 to 10−10 range by using 16-state constituent codes. However, achieving floors below 10-10 may be difficult, particularly for high code rates and/or small frame sizes. There are PCCC variants that have improved floors, such as concatenating more than two constituent codes, but only at the expense of increased complexity. PCCCs have high complexity code constraints. With 8- or 16-state constituent codes the PCCC decoder complexity is rather high. PCCCs generally have fast convergence that is amongst the fastest of all TLCs. Typically only 4-8 iterations are required. PCCCs generally have fair code rate flexibility. Code rate flexibility is easily achieved by puncturing the outputs of the constituent codes, as is well known in the art. However, for very high code rates the amount of puncturing required is rather high, which degrades performance and increases decoder complexity. PCCCs have good frame size flexibility. The frame size may be modified by changing the size of the interleaver, and there exist many flexible interleaver algorithms that achieve good performance. PCCCs generally have good modulation flexibility. Systematic bits and the parity bits from each constituent code generally need to combined and mapped to the signal set.
FIG. 3 is an illustrative block diagram of an encoder for a SCCC which involves the serial concatenation of two convolutional codes. The outer encoder is fed the frame of information bits, and its encoded output is interleaved before being input to the inner encoder. The encoded outputs of only the inner encoder must be mapped to the signal set used on the channel. SCCCs generally have medium threshold performance. The threshold performance of SCCCs is typically 0.3 dB worse than PCCCs. SCCCs generally have good floor performance that is amongst the best of all TLCs. With SCCCs, it is possible to have BER floors in the range 10−8 to 10−10 with 4-state constituent codes, and below 10−10 with 8-state constituent codes. However floor performance is degraded with high code rates. SCCCs generally have medium complexity code constraints. Code complexity constraints are typically low, but are higher for high code rates. Also, constituent decoder complexity is higher than for the equivalent code in a PCCC because soft decisions of both systematic and parity bits must be formed. SCCCs generally have fast convergence. The convergence may be even faster than that of PCCCs, typically with 4-6 iterations required. However, SCCCs have poor code rate flexibility. As in the case of PCCCs, SCCCs typically accomplish rate flexibility by puncturing the outputs of the constituent encoders. However, due to the serial concatenation of constituent codes, the amount of puncturing is typically required to be higher for SCCCs than for PCCCs, for an equivalent overall code rate. SCCCs generally have good frame size flexibility. As in the case of PCCCs, SCCCs accomplish frame size flexibility by changing the size of the interleaver. However, for equivalent information frame sizes the interleaver of an SCCC is generally larger than that of a PCCC. Consequently, there is a complexity penalty in SCCCs for large frame sizes. Also, if the code rate is adjusted by puncturing the outer code then the interleaver size will depend on both the code rate and frame size, which complicates reconfigurability. Finally, SCCCs generally have very good modulation flexibility. This is because the inner code on an SCCC is connected directly to the channel it is relatively simple to map the bits into the signal set.
FIG. 4 is an illustrative block diagram of an encoder for a LDPC which involves block codes defined by a sparse parity check matrix. This sparseness admits a low complexity iterative decoding algorithm. The generator matrix corresponding to this parity check matrix can be determined, and used to encode a frame of information bits. These encoded bits must then be mapped to the signal set used on the channel, as shown in FIG. 4. LDPCs generally have good threshold performance. LDPCs have been reported that have threshold performance within a tiny fraction of a dB of the Shannon Limit. However, for practical decoders their threshold performance is usually comparable to that of PCCCs. LDPCs generally have medium floor performance. Floor performance for LDPCs are typically better than PCCCs, but worse than SCCCs. LDPCs generally have low complexity code constraints. In fact, LDPCs typically have the lowest complexity code constraints of all TLCs. However, high throughput LDPC decoders require large routing resources or inefficient memory architectures, which may dominate decoder complexity. Also, LPDC encoders are typically a lot more complex than other TLC encoders. LDPCs generally have slow convergence. LDPC decoders typically have the slowest convergence of all TLCs. Many published results are for 100 iterations or more. However, practical LDPC decoders will typically use 20-30 iterations. LDPCs generally have good code rate flexibility. However, LDPCs generally have poor frame size flexibility. For LDPCs to change frame size, they must change their parity check matrix, which may be quite difficult in a practical, high throughput decoder. LDPCs generally have good modulation flexibility. As in the case of PCCCs, output bits of LDPCs generally need to be mapped into signal sets of a modulation scheme.
FIG. 5 is an illustrative block diagram of an encoder for a TPC involving the arrangement of information bits as an array of equal length rows and equal length columns. The rows are encoded by one block code, and then the columns (including the parity bits generated by the first encoding) are encoded by a second block code. The encoded bits must then be mapped into the signal set of the channel. TPCs generally have poor threshold performance. In fact, TPCs typically have the worst threshold performance of all TLCs. TPCs can have thresholds that are as much as 1 dB worse than PCCCs. However, for very high code rates, e.g., 0.95 and above, they will typically outperform other TLCs. TPCs have medium floor performance. The floor performance of TPC is typically lower than that of PCCCs, but not as low as that of SCCCs. TPCs generally have low complexity code constraints. TPC decoders typically have the lowest complexity of all TLCs, and high throughput parallel decoders can readily be constructed. TPCs generally have medium convergence. TPC decoders typically require 8-16 iterations to converge. However, TPCs generally have poor rate flexibility. The overall rate of a TPC is typically dictated by the rate of its constituent codes. There is some flexibility available in these rates, but it is often very difficult to choose an arbitrary rate. TPCs also generally have poor frame size flexibility. The overall frame size of a TPC is also typically dictated by the frame size of its constituent codes. It is often difficult to choose an arbitrary frame size, and especially difficult to choose an arbitrary code rate and an arbitrary frame size. Finally, TPCs generally have good modulation flexibility. As in the case of PCCCs and LDPCs, output bits of TPCs generally need to be mapped into signal sets of a modulation scheme.
In the various TLCs described above, lack of flexibility is typically a serious concern. That is, high levels of performance is usually only achieved for a limited range of code rates, frame sizes, or modulation types. Operation outside of this limited range results in degraded performance or significantly increased complexity. Furthermore, it is more difficult to achieve high data throughputs with Turbo-like code decoders compared to decoders for more traditional FEC schemes. There is a demand in modern communication and storage systems for a very flexible error correction solution that does not compromise performance and can achieve high data throughputs.